package com.lw.leetcode.dp.c;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 1681. 最小不兼容性
 * c
 * dp
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/30 14:01
 */
public class MinimumIncompatibility {

    public static void main(String[] args) {
        MinimumIncompatibility test = new MinimumIncompatibility();

        // 4
//        int[] nums = {1,2,1,4};
//        int k = 2;

        // 6
//        int[] nums = {6, 3, 8, 1, 3, 1, 2, 2};
//        int k = 4;

        // -1
//        int[] nums = {5, 3, 3, 6, 3, 3};
//        int k = 3;

        // 12
//        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
//        int k = 8;

        // 21
//        int[] nums = {1, 2, 2, 2, 4, 4, 8, 9, 10, 10, 10, 11};
//        int k = 4;

        // 0
        int[] nums = {1, 2};
        int k = 2;

        long l = System.currentTimeMillis();
        int i = test.minimumIncompatibility(nums, k);
        System.out.println(i);
//        System.out.println(System.currentTimeMillis() - l);
    }

    public int minimumIncompatibility(int[] nums, int k) {
        Arrays.sort(nums);
        int length = nums.length;
        if (k == 1) {
            int item = -1;
            for (int num : nums) {
                if (item == num) {
                    return -1;
                }
                item = num;
            }
            return nums[length - 1] - nums[0];
        }
        int l = 1 << length;
        int[] arr = new int[l];
        Arrays.fill(arr, -1);
        int t = length / k;
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i < l; i++) {
            int c = Integer.bitCount(i);
            if (c % t != 0) {
                continue;
            }
            if (c == t) {
                int a = -1;
                int n = i;
                int index = 0;
                int last = -1;
                int v = -1;
                while (n != 0) {
                    if ((n & 1) == 1) {
                        if (nums[index] == last) {
                            v = -1;
                            break;
                        }
                        last = nums[index];
                        if (a == -1) {
                            a = last;
                            v = 0;
                        } else {
                            v = last - a;
                        }
                    }
                    n >>= 1;
                    index++;
                }
                if (v != -1) {
                    list.add(i);
                    arr[i] = v;
                }
            } else {
                int min = Integer.MAX_VALUE;
                for (int key : list) {
                    if ((i | key) != i) {
                        continue;
                    }
                    if (arr[i - key] != -1 && arr[key] != -1) {
                        min = Math.min(min, arr[i - key] + arr[key]);
                    }
                }
                arr[i] = min == Integer.MAX_VALUE ? -1 : min;
            }
        }
        return arr[l - 1];
    }

}
